package com.learn.acm.three;

import com.google.gson.Gson;
import org.junit.jupiter.api.Test;

/**
 *
 *
 给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

 示例 1:

 输入: 2
 输出: [0,1,1]
 示例 2:

 输入: 5
 输出: [0,1,1,2,1,2]
 */
public class Solution338 {


    public int[] countBits(int num) {
        if (num <= 0) return new int[]{0};
        if (num == 1) return new int[]{0,1};
        int[] result = new int[num+1];
        result[0] = 0;
        result[1] = 1;
        int abs = 0;
        int pre = 1;
        for (int i = 2;i<=num;i++) {
            if (2 << abs == i) {
                pre = 2<<abs;
                abs++;
                result[i] = 1;
            } else {
                result[i] = result[i-pre] + 1;
            }
        }
        return result;
    }


    @Test
    public void test() {

        System.out.println(new Gson().toJson(countBits(10)));
    }
}
